package summary;

import java.util.Stack;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/6 21:54
 */
public class Title42 {

    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int capacity = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int middle = stack.pop();
                if (!stack.isEmpty()) {
                    int left = stack.peek();
                    int h = Math.min(height[left], height[i])- height[middle];
                    int w = i - left - 1;
                    capacity += h * w ;
                }
            }
            stack.push(i);
        }
        return capacity;
    }

    public static void main(String[] args) {

    }
}
